package ch05.d1;

import org.junit.Test;

import java.util.Arrays;

public class ArraySortTest {

//    @Test
//    public void test1(){
//        //冒泡排序
//        int[] a=new int[100000];
//        for (int i = 0; i < a.length; i++) {
//            a[i]=(int)(Math.random()*100000);
//        }
//        long l1=System.currentTimeMillis(); //获取当前时间
//        for (int i = 0; i < a.length-1; i++) {//4
//            for (int j = 0; j < a.length-1-i; j++) {//4
//                //j j+1 比较 逆序则交换
//                if(a[j] < a[j+1]){
//                    int t=a[j];
//                    a[j]=a[j+1];
//                    a[j+1]=t;
//                }
//            }
//        }
//        long l2=System.currentTimeMillis();
//        System.out.print("冒泡排序结果：");
//        System.out.println(l2-l1);
//    }
    @Test
    public void test2(){
        //冒泡排序
        int[] a=new int[100000000];
        for (int i = 0; i < a.length; i++) {
            a[i]=(int)(Math.random()*10000000);
        }
        long l1=System.currentTimeMillis(); //获取当前时间

        // shell法排序
        int j = 0;
        int temp = 0;
        // 分组
        for(int increment = a.length / 2; increment > 0; increment /=2) {
            // 每个组内排序
            for (int i = increment; i < a.length; i++) {
                temp = a[i];
                for (j = i; j >= increment; j -= increment) {
                    if (temp < a[j - increment]) {
                        a[j] = a[j - increment];
                    } else {
                        break;
                    }
                }
                a[j] = temp;
            }
        }

        long l2=System.currentTimeMillis();
        System.out.print("希尔排序结果：");
        System.out.println(l2-l1);
    }

    @Test
    public void test3(){
        //冒泡排序
        int[] a=new int[100000000];
        for (int i = 0; i < a.length; i++) {
            a[i]=(int)(Math.random()*10000000);
        }
        long l1=System.currentTimeMillis(); //获取当前时间
        //快排
        Arrays.sort(a);

        long l2=System.currentTimeMillis();
        System.out.print("jdk快速排序结果：");
        System.out.println(l2-l1);
    }
    @Test
    public void test4(){
        //冒泡排序
        int[] a=new int[100000000];
        for (int i = 0; i < a.length; i++) {
            a[i]=(int)(Math.random()*10000000);
        }
        long l1=System.currentTimeMillis(); //获取当前时间
        //快排
        quickSort(a,0,a.length-1);


        long l2=System.currentTimeMillis();
        System.out.print("快速排序结果：");
        System.out.println(l2-l1);

    }
    public void quickSort(int[] a,int low,int high){

        byte b=10;
        int x=b;

        int pivot=a[low];//基准值
        int left=low;
        int right=high;

        while(left<right){
            // 右侧遍历
            while(left<right && a[right]>=pivot){
                right--;
            }

            // 左侧遍历
            while(left<right && a[left]<=pivot){
                left++;
            }

            // 交换
            if(left<right){
                int temp=a[left];
                a[left]=a[right];
                a[right]=temp;
            }
        }
        // 基准值归位
        a[low]=a[left];
        a[left]=pivot;
        //左侧遍历
        if(low<left){
            quickSort( a,low,left-1);
        }
        // 右侧遍历
        if(right<high){
            quickSort(a, right+1 ,high );
        }


    }



}
